#include "algorithm_genetic.h"


/** Pocita reseni daneho problemu pomoci trifazoveho genetickeho algoritmu.
 * 1. Prci dolni odhad sirky frekvencniho pasma z poctu pozadavku nejvetsi anteny a te
 * antene priradi frekvence az do dolniho odhadu (v pravidelnych co nejmensich intervalech).
 * 2. Pokusi se sekvencne priradit frekvence vsem vysilacum v "kritickem" uzemi okolo nejvetsi anteny.
 * Pouziva pouze frekvence do dolniho odhadu.
 * 3. Na nevybrane vysilace spusti geneticky algoritmus, ktery vytvari poradi vysilacu pro sekvencni
 * algoritmus.
 * Pozn. V upravenem algoritmu jsou prvni dva kroky vynechany.
 * \return true, pokud se povedlo vytvorit korektni prirazeni
 */
bool GeneticAlgorithm::Solve() {

	// pokus - pokusim se provest jen REA a FEA, jestli nahodou nebudou lepsi nez muj nejchytrejsi algoritmus

	// seradit podle node-degree a pak provest :)
	int * best = 0;
	int max = CountDegree();
	if (!options->original) { // upraveny algoritmus
		bool * chosen = new bool[area->CELLS_CNT];
		for (int i = 0; i < area->CELLS_CNT; ++i) chosen[i] = true;
		int b_size = 0;
		best = CreateOrderedList(chosen, b_size);
		// ted provedu horni odhad pomoci REA a FEA - do tohoto horniho odhadu budu dal prirazovat frekvence
		frequencies = 100;
		int min = MAXINT;
		while (min == MAXINT) {
			frequencies *= 10;
			area->setFrequencyCount(frequencies);
			area->save();
			int fea, rea;
			if (REA(best, b_size) == 0) {
				rea = *(std::max_element(area->calls, area->calls + area->size));
				options->Log() << "REA mi spocital minimalni pocet frekvenci: " << rea << std::endl;
				Print(area->sortedCalls());
				min = rea;
			}
			else options->Log() << "REA se nepovedlo priradit vsechny cally!" << std::endl;

			area->load();
			if (AssignFrequencies(best, b_size) == 0) {
				fea = *(std::max_element(area->calls, area->calls + area->size));
				if (fea < min) {
					options->Log() << "FEA mi spocital minimalni pocet frekvenci: " << fea << std::endl;
					Print(area->sortedCalls());
					min = fea;
				}
				else options->Log() << "FEA dopocitalo, ale dopadlo hure: " << fea << std::endl;
			}
			else options->Log() << "FEA se nepovedlo priradit vsechny cally!" << std::endl;
			area->load();
		}
		delete[] chosen;
		//area->setFrequencyCount(frequencies = min); // takovehle minimum mi spocitalo hloupe prirazeni
		options->Log() << "Po hloupem prirazeni (podle node-degree ordering) mam maximum frekvenci nastaveno na: " << min << std::endl;
		// nastavim pocet frekvenci na ulozene maximum a budu pracovat jenom v nem
		area->setFrequencyCount(frequencies = min);
	}
	else { // puvodni algoritmus
		// nacteni vstupu a urceni dolniho odhadu
		options->Log() << "Nacteni vstupu: " << timer->lap() << std::endl;
		PrintInfo();
		options->Log() << "1/3 Zacina faze pravidelneho prirazeni" << std::endl;
		Regular();
		area->save();
		options->Log() << "Pravidelne prirazeni: " << timer->lap() << std::endl;
		Print();


		// hladovy algoritmus - pouze do dolniho odhadu, horni odhad vyuziji az u genetickeho
		options->Log() << "2/3 Zacina faze hladoveho algoritmu" << std::endl;
		bool * chosen = new bool[area->CELLS_CNT];
		for (int i = 0; i < area->CELLS_CNT; ++i) chosen[i] = false;
		chosen[max] = true;
		if (!Greedy(chosen)) {
			options->Log() << " Nepovedlo se nic priradit hladovym algoritmem!" << std::endl;
		}
		else {
			int size = 0;
			for (int i = 0; i < area->CELLS_CNT; ++i) if (chosen[i]) ++size;
			options->Log() << " Hladovy algoritmus uspel - priradil celkem " << size << " polim vsechny frekvence." << std::endl;
		}
		delete[] chosen;
		options->Log() << "Hladovy algoritmus: " << timer->lap() << std::endl;
		Print();
	}

	area->save();
	// geneticky algoritmus
	options->Log() << "3/3 Zacina faze genetickeho algoritmu" << std::endl;
	Genetic(best);
	//Print();

	// setridit seznamy, abych to mohl vytisknout citelne
	//options->Log() << "Setrizene pridelene frekvence:" << std::endl;
	//Print(area->sortedCalls());
	if (best != 0) {
		delete[] best;
	}


	options->Log() << "Celkova doba: " << timer->total() << std::endl;
	return true;
}

/** Spocte stupne vsech anten. Stupen je pocet vysilacu, se kterymi tvori vysilace na aktualne vybrane
 * antene omezeni - musi byt frekvencne oddeleny.
 * \return int nejvetsi ze vsech stupnu anten
 */
int GeneticAlgorithm::CountDegree() {
	int max, max_value = 0, degree;
	for (int i = 0; i < area->CELLS_CNT; ++i) {
		degree = 0;
		for (int j = 0; j < area->CELLS_CNT; ++j) {
			degree += area->cells[j].demand * area->frequencyDistance(i, j);
		}
		area->cells[i].info = degree;
		if (degree > max_value) {
			max_value = degree;
			max = i;
		}
	}
	return max;
}

/** Faze pravidelneho prirazeni. Priradi frekvence antena s nejvice vysilaci v co nejmensich intervalech.
 */
void GeneticAlgorithm::Regular() {
	int max, max_value = 0;
	for (int i = 0; i < area->CELLS_CNT; ++i) {
		if (area->cells[i].demand > max_value) {
			max = i;
			max_value = area->cells[i].demand;
		}
	}
	int i = area->cells[max].index, d = area->reuse_size - 1;
	frequencies = (max_value - 1) * d + 1;
	area->setFrequencyCount(frequencies);

	options->Log() << "Nejvetsi pozadavek: " << max_value << ", bunka: " << max << ", pocet frekvenci: " << frequencies << std::endl;
	for (int f = 0; f < max_value; ++f) {
		area->assignCall(i + f, f * d + 1, max);
	}
}

/** Vytvori poradi vysilacu setridene sestupne podle jejich stupne. Pouziva se pri hladovem prirazeni kritickeho uzemi.
 * \param chosen vysilace, ktere se maji vyskytovat v serazenem seznamu
 * \param call_size vytvoreny pocet vysilacu
 * \return serazeny seznam vysilacu
 */
int * GeneticAlgorithm::CreateOrderedList(bool * chosen, int & call_size) {
	std::multimap<int, int> region;
	for (int i = 0; i < area->CELLS_CNT; ++i) {
		if (chosen[i]) {
			region.insert(std::pair<int, int>(area->cells[i].info, i));
			call_size += area->cells[i].demand;
			options->Log() << i + 1 << " ";
		}
	}
	options->Log() << std::endl;
	// vytvorit seznam callu - indexu frekvenci, ktere se maji nastavit
	int * call_list = new int[call_size], max, cnt = 0;
	std::list<int> reverse;
	for (std::multimap<int, int>::const_iterator c = region.begin(); c != region.end(); ++c) {
		reverse.push_front(c->second);
	}
	for (std::list<int>::const_iterator c = reverse.begin(); c != reverse.end(); ++c) {
		max = area->cells[*c].index + area->cells[*c].demand;
		for (int j = area->cells[*c].index; j < max; ++j) {
			call_list[cnt++] = j;
		}
	}
	return call_list;
}

/** Faze hladoveho prirazeni v kritickem uzemi. Vytvori seznam vysilacu v kritickem uzemi a pote
 * se jim v poradi podle jejich stupne pokusi priradit frekvence.
 * \param chosen seznam vybranych vysilacu v minulem kroku
 * \return true, pokud se povedlo priradit
 */
bool GeneticAlgorithm::Greedy(bool * chosen) {
	options->Log() << " Vstupni region: " << std::endl << "  ";
	int i, size = 0;
	for (i = 0; i < area->CELLS_CNT; ++i) if (chosen[i]) ++size;
	if (size != area->CELLS_CNT) {
		bool * old = new bool[area->CELLS_CNT];
		memcpy(old, chosen, area->CELLS_CNT);
		// pokud nejsou v regionu vsechna pole, tak rozsir region o vsechny sousedy
		for (i = 0; i < area->CELLS_CNT; ++i) {
			if (old[i]) {
				options->Log() << i + 1 << " ";
				for (std::vector<int>::const_iterator j = area->cells[i].neighbours.begin(); j != area->cells[i].neighbours.end(); ++j) {
					chosen[*j] = true;
				}
			}
		}
		delete[] old;
	}
	else {
		return false;
	}
	options->Log() << std::endl;
	options->Log() << " -> Novy region: " << std::endl << "  ";
	// spocist velikost pole callu a setridit bunky podle spocteneho node-degree
	int call_size = 0;
	int * call_list = CreateOrderedList(chosen, call_size);

	if (AssignFrequencies(call_list, call_size, true) != 0) {
		Print();
		delete[] call_list;
		area->load();
		return Greedy(chosen);
	}
	else {
		delete[] call_list;
		return true;
	}
}

/** Geneticka faze genetickeho algoritmu. Nahodne vytvori prvotni populaci - nahodne setridene
 * vysilace. Tyto permutace pote mutuje, vybira z nich ty lepsi a zbyle doplnuje krizenim ponechanych.
 * Vysledkem je nejlepsi setrideni vysilacu jako vstup do sekvencniho algoritmu
 * \param best_sequential pamet pro ulozeni nejlepsiho reseni
 */
void GeneticAlgorithm::Genetic(int * best_sequential) {
	// vyrobi se seznam nepridelenych callu, ten se nahodne zamicha - nekolikrat
	int size = 0, ** generation, max_fitness, min_fitness;
	double * fitness;
	for (int i = 0; i < area->size; ++i) {
		if (area->calls[i] == 0) ++size;
	}
	if (size == 0) {
		options->Log() << "Vse je jiz vyreseno pomoci hladove faze, nemam co pocitat." << std::endl;
		return;
	}
	else {
		options->Log() << "Delka jednoho genu: " << size << std::endl;
	}
	options->Display("GENEROVANI");
	generation = Generate(size);
	// mam generaci, ted pro kazde individuum spoctu fitness = kolik callu mi zbyva
	PrintGeneration(generation, size);
	options->Log() << "Generovani: " << timer->lap() << std::endl;
	options->Display("GENETICKY ");
	options->NewDisplay();
	options->Display("horsi nez seq: " + IntToStr(frequencies));
	fitness = new double[options->generation_size];
	double sum_fitness;
	int * best = new int[size];
	int * positions = new int[area->size + 1];
	// budou mne zajimat jen ta individua, ktera jsou lepsi nez zatim hloupe namerene maximum
	int f, best_fitness, best_fitness_index;
	bool best_found = false;

	if (options->original) best_fitness = MAXINT;
	else best_fitness = frequencies;

// odsud opakovat, dokud nenajdu dostatecne dobrou generaci
	options->Log() << "Generation;Min fitness;Max fitness;Left genes;" << std::endl;
	for (int g = 0; g < options->generation_count; ++g) {
		best_fitness_index = -1;
		max_fitness = 0;
		min_fitness = MAXINT;
		sum_fitness = 0;
		options->Log() << g + 1 << ";";
		for (int i = 0; i < options->generation_size; ++i) {
			// stara verze programu, ktera pocitala s malym minimem
			if (options->original) {
				if ((f = AssignFrequencies(generation[i], size)) == 0) {
					options->Log() << std::endl << "Final individuum: " << i + 1 << std::endl;
					best_fitness = 0;
					for (int i = 0; i < size; ++i) {
						best[i] = generation[best_fitness_index][i];
					}
					break;
				}
			}
			else {
				if (f = AssignFrequencies(generation[i], size) == 0) f = *(std::max_element(area->calls, area->calls + area->size));
				else f = f * BLOCKED_MULTIPLIER + frequencies;
			}
			// v f mam ulozen pocet blokovanych - v novem pripade je to pocet frekvenci, ve sterem je to pocet blokovanych frekvenci
			if (f > max_fitness) max_fitness = f;
			if (f < min_fitness) {
				min_fitness = f;
				if (f < best_fitness) {
					best_found = true;
					best_fitness = f;
					best_fitness_index = i;
				}
			}
			fitness[i] = f;
			area->load();
		}
		// ulozim si historicky nejlepsiho jedince
		if (best_fitness_index != -1) {
			for (int i = 0; i < size; ++i) {
				best[i] = generation[best_fitness_index][i];
				options->Display(IntToStr(best_fitness - 1));
			}
		}
		// nastavime nejvetsi pravdepodobnost zachovani na 90 %
		// sum_fitness /= (int)(0.9 * sum_fitness) / max_fitness;
		// spocitam, zda individuum prejde do celku nebo ne
		int posunuti = 1; // cim je mensi, tim maji lepsi jedinci vetsi sanci byt vybrani, je zde proto, ze rozsah individui je hrozne maly
		sum_fitness = 0;
		for (int i = 0; i < options->generation_size; ++i) {
			fitness[i] = 1 / (fitness[i] - min_fitness + posunuti);
			sum_fitness += fitness[i];
		}
		sum_fitness = options->generation_size / (2 * sum_fitness);
		int selected = 0;
		double percent;
		std::vector<int> selected_index;
		for (int i = 0; i < options->generation_size; ++i) {
			percent = fitness[i] * sum_fitness;
			if ((double)rand() / RAND_MAX < percent) {
				fitness[i] = 1;
				selected_index.push_back(i);
				++selected;
			}
			else {
				fitness[i] = 0;
			}
		}
		if (selected == 0) {
			fitness[0] = 1;
			selected_index.push_back(0);
			selected = 1;
		}
		options->Log() << min_fitness << ";" << max_fitness << ";" << selected << ";" << std::endl;
		// prvky oznacene 1 jsou vybrany do dalsi generace - na odpovidajici indexy provedu mutaci
		for (std::vector<int>::const_iterator i = selected_index.begin(); i != selected_index.end(); ++i) {
			Mutate(generation[*i], size);
		}
		// prvky oznacene 0 neprosly sitem - doplnim misto nich nove pomoci crossoveru na ty dobre
		for (int i = 0; i < options->generation_size; ++i) {
			if (fitness[i] == 0) {
				int parent1 = selected_index[RandomNumber(selected)];
				int parent2 = selected_index[RandomNumber(selected)];
				CrossOver(generation[parent1], generation[parent2], positions, generation[i], size);
			}
		}
	}
	
	// nenasel jsem lepsi prirazeni nez na zacatku
	if (!best_found) {
		options->Log() << "Pomoci genetickeho algoritmu se nepovedlo spocitat lepsi reseni, nez dokazalo hloupe prirazeni. Minimum je tedy: " << frequencies << std::endl;
		if (best_sequential != 0) {
			for (int i = 0; i < size; ++i) {
				best[i] = best_sequential[i];
			}
		}
		else {
			// pouziji prvni gen
			for (int i = 0; i < size; ++i) {
				best[i] = generation[0][i];
			}			
		}
	}

	// pokud jsem nasel individuum s mensim poctem frekvenci nez mam prideleno, tak ho vypisu a vesele skoncim
	int fea = MAXINT, rea = MAXINT;
	if (options->original) {
		// v puvodnim algoritmu musime jeste dopocitat, kolik tedy frekvenci bude potreba a zjistit, ktery z algoritmu (REA, FEA) je na to lepsi
		area->setFrequencyCount(frequencies += best_fitness * (area->reuse_size - 1)); // zvysim pocet frekvenci o maximalni mozny pocet zablokovanych callu
	}
	
	area->load();
	if (REA(best, size) == 0) {
		rea = *(std::max_element(area->calls, area->calls + area->size));
	}
	area->load();
	if (AssignFrequencies(best, size) == 0) {
		fea = *(std::max_element(area->calls, area->calls + area->size));
	}

	if (rea < fea) {
		frequencies = rea;
		options->Log() << "Finalni prirazeni pomoci REA - " << frequencies << ", FEA ( " << fea << ")" << std::endl;
		area->load();
		REA(best, size);
	}
	else {
		options->Log() << "Finalni prirazeni pomoci FEA - " << frequencies << ", REA ( " << rea << ")" << std::endl;
		frequencies = fea;
	}


	// uklidit si po sobe!
	for (int i = 0; i < options->generation_size; ++i) {
		delete[] generation[i];
	}
	delete[] generation;

	delete[] best;
	delete[] positions;
	delete[] fitness;
}

/** Vygeneruje pozadovany pocet reseni (poradi jeste neprirazenych vysilacu).
 * \param cnt pocet neprirazenych vysilacu
 * \return populace vsech reseni
 */
int ** GeneticAlgorithm::Generate(int cnt) {
	int * call_list, ** generation;
	call_list = new int[cnt];
	generation = new int *[options->generation_size];
	cnt = 0;
	for (int i = 0; i < area->size; ++i) {
		if (area->calls[i] == 0) call_list[cnt++] = i;
	}
	for (int i = 0; i < options->generation_size; ++i) {
		generation[i] = MixArray(call_list, cnt);
	}
	delete[] call_list;
	return generation;
}

/** Mutacni operator. Prochazi vsechny geny v chromozomu, u kazdeho nahodne urci, zda ma byt
 * zmutovan. Pokud ano, pak prohodi jeho sousedy i obsousedy.
 * \param individual mutovany chromozom
 * \param size velikost chromozomu
 */
void GeneticAlgorithm::Mutate(int * individual, int size) {
	for (int j = 2; j < size - 2; ++j) {
		if (((double)rand() / RAND_MAX) < options->mutation_rate) {
			std::swap(individual[j - 1], individual[j + 1]);
			std::swap(individual[j - 2], individual[j + 2]);
		}
	}
}

/** Provede permutacni crossover danych rodicu a vytvori jejich potomka.
 * \param p1 prvni rodic
 * \param p2 druhy rodic
 * \param positions pomocne pole
 * \param individual vzinkly potomek
 * \param size delka chromozomu (pocet neprirazenych vysilacu)
 */
void GeneticAlgorithm::CrossOver(int * p1, int * p2, int * positions, int * individual, int size) {
	// spocitam si, ktere cislo je na jake pozici
	for (int j = 0; j < size; ++j) {
		positions[p2[j]] = j;
		individual[j] = -1;
	}
	std::map<int, int> order;
	// vyplnuju bin. vektor - pokud mi vyjde 0, tak odpovidajici cislici budu muset dat na cislo podle pomocneho pole
	for (int j = 0; j < size; ++j) {
		if (rand() < RAND_MAX / 2) { // 0
			order[positions[p1[j]]] = p1[j];
		}
		else { // 1
			individual[j] = p1[j];
		}
	}
	// doplnim prazdna mista v individuu
	int i = 0;
	for (std::map<int, int>::const_iterator j = order.begin(); j != order.end(); ++j) {
		for (; individual[i] != -1; ++i);
		individual[i] = j->second;
	}
}


/** Nahodne promicha dane pole.
 * \param a promichavane pole
 * \param size velikost pole
 * \return nahodne promichane pole z hodnotama ze vstupniho pole
 */
int * GeneticAlgorithm::MixArray(int * a, int size) {
	int * mixed = new int[size];
	for (int i = 0; i < size; ++i) {
		mixed[i] = a[i];
	}
	int i, j, d;
	for (int changes = RandomNumber(size * 10, size); changes > 0; --changes) {
		i = RandomNumber(size);
		j = RandomNumber(size);
		d = mixed[i];
		mixed[i] = mixed[j];
		mixed[j] = d;
		//std::swap(mixed[i], mixed[j]);
	}
	return mixed;
}

/** Algoritmus Frequency Exhaustive Assignment (sekvencni algoritmus).
 * Snazi se priradit vsem polim v seznamu nejakou frekvenci ze vsech moznych frekvenci. Prochazi
 * seznam vysilacu a v tomto poradi jim prirazuje nejmensi mozne frekvence.
 * \param call_list poradi vysilacu
 * \param size pocet vysilacu
 * \param break_on_fail - pokud je true, tak se pri prvnim neuspesnem prirazeni vzda dalsi prace, jinak priradi i ostatnim
 * \return pocet vysilacu bez prirazene frekvence
 */
int GeneticAlgorithm::AssignFrequencies(int * call_list, int size, bool break_on_fail) {
	bool fail;
	int blocks = 0, cell;
	for (int i = 0; i < size; ++i) {
		if (area->calls[call_list[i]] != 0) continue;
		fail = true;
		cell = -1;
		area->findCell(call_list[i], cell);
		for (int f = 1; f <= frequencies; ++f) {
			if (area->assignCall(call_list[i], f, cell)) {
				fail = false;
				break;
			}
		}
		if (fail) {
			if (break_on_fail) {
				options->Log() << "Nepovedlo se priradit bunce " << cell + 1 << std::endl;
				return 1;
			}
			else ++blocks;
		}
	}
	return blocks;
}


/** Algoritmu Requirement Exhaustive Assignment (alternativni sekvencni algoritmus).
 * Prochazi seznam frekvenci a pokousi se je priradit vsem vysilacum bez frekvence (
 * nejprve se vsem pokusi priradit 1., pote zbylym druhou, atd.).
 * \param call_list poradi vysilacu
 * \param size pocet vysilacu
 * \return pocet vysilacu bez prirazene frekvence
 */
int GeneticAlgorithm::REA(int * call_list, int size) {
	std::list<int> toassign(call_list, call_list + size);
	std::list<int>::iterator i;
	// vypustit vsechny uz pridelene bunky
	for (i = toassign.begin(); i != toassign.end();) {
		if (area->calls[*i] != 0)	i = toassign.erase(i);
		else ++i;
	}

	int blocks = 0;
	for (int f = 1; f <= frequencies && !toassign.empty(); ++f) {
		for (i = toassign.begin(); i != toassign.end();) {
			if (area->assignCall(*i, f)) i = toassign.erase(i);
			else ++i;
		}
	}
	return (int)(toassign.size());
}

/** Vypise do logu celou populaci.
 * \param generation populace
 * \param size delka jednoho chromozomu
 */
void GeneticAlgorithm::PrintGeneration(int ** generation, int size) {
	options->Log() << "Vypis generace: " << std::endl;
	for (int i = 0; i < options->generation_size; ++i) {
		options->Log() << std::setw(4) << i + 1 << " | ";
		for (int j = 0; j < size; ++j) {
			options->Log() << std::setw(4) << generation[i][j];
		}
		options->Log() << std::endl;
	}
}
